package Aleehot100;

/**
 * ClassName: c029
 * Package: Aleehot100
 * Description: 删除链表的倒数第n个节点
 *
 * @Author BCXJ
 * @Create 2025/6/17 08:48
 * @Version 1.0
 * @Since 1.0
 */
public class c029 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        listNode1.next = listNode2;
        removeNthFromEnd(listNode1, 2);

    }
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 健壮性判断
        if(head == null) {
            return head;
        }

        // 快慢指针法
        ListNode fast = head, slow = head;
        for (int i = 0; i < n - 1 && fast != null; i++) {
            fast = fast.next;
        }
        if(fast == null) {
            return head;
        }

        // 同步位移
        ListNode pre = null;
        while(fast.next != null) {
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }

        // 删除slow 节点
        if(pre != null) {
            pre.next = slow.next;
        } else {
            head = head.next;
        }
        slow.next = null;
        return head;
    }
}
